import collections


class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        length = len(tasks)
        table = collections.Counter(tasks)
        max_count = max(table.values())
        max_budgets = length // (n + 1) if length % (n + 1) == 0 else length // (n + 1) + 1
        budgets = max(max_count, max_budgets)
        if max_count < max_budgets:
            return length
        else:
            max_key_num = 0
            for key in table:
                if table[key] == max_count:
                    max_key_num += 1
            return max((budgets - 1) * (n + 1) + max_key_num, length)



data = Solution()
tasks = ["A", "A", "A", "B", "B", "B", "C", "C", "C", "D", "D"]
n = 5
print(data.leastInterval(tasks, n))
tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"]
n = 2
print(data.leastInterval(tasks, n))
tasks = ["A","B","A","B"]
n = 3
print(data.leastInterval(tasks, n))